package ListNode;

import java.util.Stack;

/**
 * 445. 两数相加 II
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 *
 *
 * 进阶：
 *
 * 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
 *
 *
 *
 * 示例：
 *
 * 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 8 -> 0 -> 7
 */
public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> l1s=new Stack<ListNode>();
        Stack<ListNode> l2s=new Stack<ListNode>();
        while (l1!=null){
            l1s.add(l1);
            l1=l1.next;
        }
        while (l2!=null){
            l2s.add(l2);
            l2=l2.next;
        }
        int tmp=0;
        ListNode res=null;
        while (l1s.size()>0||l2s.size()>0){
            int a= l1s.size()>0?l1s.pop().val:0;
            int b= l2s.size()>0?l2s.pop().val:0;
            int r= a+b+tmp;
            ListNode node =new ListNode(r%10);
            node.next=res;
            res=node;
            tmp =r/10;
        }
        if(tmp>0){
            ListNode node =new ListNode(tmp);
            node.next=res;
            res=node;
        }
        return res;
    }
    public static void main(String[] args){

    }

}
